#include <vector>

// 直接插入排序
// 最坏时间复杂度O(N^2) -- 逆序
// 最好时间复杂度O(N) -- 顺序有序
// 空间复杂度O(1)
// 稳定的排序
// static void insertSort(std::vector<int> &nums)
// {
//     int n = nums.size();
//     for (int i = 1; i < n; i++)
//     {
//         int end = i;
//         int tmp = nums[end];
//         // 注意这里是tmp < nums[end - 1]
//         while (end >= 1 && tmp < nums[end - 1])
//         {
//             nums[end] = nums[end - 1];
//             end--;
//         }

//         nums[end] = tmp;
//     }
// }

// static void insertSort(std::vector<int> &nums)
// {
//     int n = nums.size();
//     for (int i = 1; i < n; i++)
//     {
//         int end = i;
//         int tmp = nums[end];
//         while (end >= 1 && nums[end] < nums[end - 1])
//         {
//             std::swap(nums[end], nums[end - 1]);
//             end--;
//         }
//     }
// }

static void insertSort(std::vector<int> &nums)
{
    int n = nums.size();
    //[0,end]插入end+1 [0,end+1]有序
    for (int i = 0; i < n; i++)
    {
        int end = i;
        int tmp = nums[end + 1]; // 记录最后一个元素
        // 当目标元素为最小元素，end为-1时退出循环
        while (end >= 0)
        {
            // 如果大于tmp中的数据，就往后挪，并--end
            if (tmp < nums[end])
            {
                nums[end + 1] = nums[end];
                end--;
            }
            // 如果小于tmp中的数据，就跳出循环准备插入
            else
                break;
        }
        // 将数据插入到end的后一个位置
        nums[end + 1] = tmp;
    }
}
